package com.lzy.tricbuild2_hash;

import java.util.*;

/**
 * @ClassName: Tric
 * @Author: Li ZhenYong
 * @description: tric字典树,改造，将子节点存储的变为 有序数组、跳表、散列表、红黑树其中之一，
 * @Date: 2022-04-05 14:54
 * @Version: 1.0
 */
public class Tric {

	private TricNode root = new TricNode("/"); // 存储无意义字符

	// 往Trie树中插入一个字符串
	public void insert(String text) { // 例如：hello
		TricNode p = root;
		// 遍历插入的字符串
		for (int i = 0; i < text.length(); ++i) {
			HashMap<String, TricNode> children = p.children;
			if(!children.containsKey(text.charAt(i)+"")) {  // 说明包含当前子节点
				TricNode newNode = new TricNode(text.charAt(i)+"");
//				p.children.put(text[i], newNode);  // 不能使用 p.children，p可能为空
				children.put(text.charAt(i)+"", newNode);
			}
			p = children.get(text.charAt(i)+"");
		}
		p.isEndingChar = true;  // 当前为最后一个字符串，将标识设置为true
	}

	// 在Trie树中查找一个字符串
	public boolean find(String pattern) {
		TricNode p = root;

		for (int i = 0; i < pattern.length(); ++i) {  // 进行遍历找到，敏感词最后一个字符
			HashMap<String, TricNode> children = p.children;
			if(!children.containsKey(pattern.charAt(i)+"")) {
				return false;
			}
			p = p.children.get(pattern.charAt(i)+"");
		}

		if (p.isEndingChar == false) return false; // 不能完全匹配，只是前缀
		else return true; // 找到pattern
	}

	// 获取符合条件的模糊查询字符
	public List<String> getBlur(String pattern) {
		TricNode p = root;
		for (int i = 0; i < pattern.length(); ++i) {  // 进行遍历找到，敏感词最后一个字符
			HashMap<String, TricNode> children = p.children;

			if (!children.containsKey(pattern.charAt(i)+"")) {
				return null; // 不存在pattern
			}
			p = children.get(pattern.charAt(i)+"");
		}
		// pattern是前缀，需要将后面的都找回。
		// p下的所有不为空的节点都需要

		List<String> result = new ArrayList<>();

		getBlurArr(p,pattern,result);

		return result;
	}

	/**
	 * 获取与前缀匹配的数据
	 * @param p
	 * @param cur
	 * @param ans
	 */
	private void getBlurArr(TricNode p, String cur, List<String> ans) {
		if(null != p && p.isEndingChar) {
			ans.add(cur);
			return;
		}

		HashMap<String, TricNode> children = p.children;

		Set<String> setS = children.keySet();

		for (String s : setS) {
			if(children.containsKey(s)) {
				getBlurArr(children.get(s), cur+children.get(s).data, ans);
			}
		}
	}

	public static void main(String[] args) {
		Tric tric = new Tric();

		tric.insert("sb");
		tric.insert("你是个大sb");
		tric.insert("你是个大帅哥");
		tric.insert("憨批");
		System.out.println(tric.find("sb1"));  // false

		System.out.println(tric.getBlur("憨批"));
	}
}
